package architect.algorithn;

/**
 * KMP算法
 *
 * @author guanxin
 * @date 2018/5/8 16:12
 */

public class KMP {

    public static void main(String[] args) {
        String mainStr = "ababcabababdc";

        String patternStr = "babdc";

        int index = kmp(mainStr, patternStr);

        if (index == -1)
            System.out.println("没有匹配的字符串！");
        else
            System.out.printf("\"哈哈，找到字符啦，位置为：%d", index);
    }

    private static int kmp(String mainStr, String patternStr) {
        int i = 0;
        int j = 0;

        //计算“前缀串”和“后缀串“的next
        int[] next = getNextValue(patternStr);

        while (i < mainStr.length() && j < patternStr.length()) {
            if (j == -1 || mainStr.charAt(i) == patternStr.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j == patternStr.length())
            return i - patternStr.length();

        return -1;
    }

    private static int[] getNextValue(String patternStr) {
        //前缀串起始位置("-1"是方便计算）
        int k = -1;

        //后缀串起始位置（"-1"是方便计算）
        int j = 0;

        int[] next = new int[patternStr.length()];

        //根据公式： j=0时，next[j]=-1
        next[j] = -1;

        while (j < patternStr.length() - 1) {
            if (k == -1 || patternStr.charAt(k) == patternStr.charAt(j)) {
                //pk=pj的情况: next[j+1]=k+1 => next[j+1]=next[j]+1
                next[++j] = ++k;
            } else {
                //pk != pj 的情况:我们递推 k=next[k];
                //要么找到，要么k=-1中止
                k = next[k];
            }
        }

        return next;
    }
}
